Bài toán dừng là một bài toán quyết định về tính chất của chương trình máy tính trên một mô hình tính toán Turing-đầy đủ nhất định. Bài toán yêu cầu quyết định xem một chương trình với dữ liệu vào cho trước có dừng hay chạy mãi mãi. Trong mô hình trừu tượng này, không có bất kì một giới hạn nào về bộ nhớ hay thời gian cho máy chạy; máy có thể chạy lâu bao nhiêu cũng được, sử dụng tùy ý bộ nhớ, trước khi dừng. Câu hỏi chi là liệu chương trình cuối cùng có dừng hay không trên dữ liệu đã cho.

Ví dụ như chương trình sau dưới dạng mã giả

không bao giờ dừng, nó lặp lại mãi mãi. Trong khi đó, chương trình sau

dừng rất nhanh.

Chương trình càng phức tạp thì càng khó để phân tích. Ta có thể chạy chương trình một thời gian. Tuy nhiên, nếu nó không dừng trong thời gian đó thì cũng không thể biết được nó có chạy mãi mãi hay không. Turing chứng minh rằng không một thuật toán nào có thể quyết định đúng cho mọi cặp chương trình và dữ liệu vào, liệu chương trình có dừng hay không trên dữ liệu đã cho.